#pragma once

#ifndef INC_02_MERGE_SORT_H
#define INC_02_MERGE_SORT_H
#include <iostream>
#include <algorithm>
#include "TestSortHelper.h"
#include "InsertSort.h"

using namespace std;

//[l,mid] [mid+1,r]归并
//优化，辅助数组t不递归生成，不然要gg
template <typename T>
void __merge(T t[], T arr[], int left, int mid, int r) {
	for (int i = left;i <= r;i++) {
		t[i - left] = arr[i];
	}

	int i = left - left;
	int k = left;
	int j = mid + 1 - left;

	while (i <= mid - left && j <= r - left) {
		if (t[i] < t[j]) {
			arr[k] = t[i];
			i++;
		}
		else {
			arr[k] = t[j];
			j++;
		}
		k++;
	}

	while (i <= mid - left) {
		arr[k] = t[i];
		i++;
		k++;
	}

	while (j <= r - left) {
		arr[k] = t[j];
		j++;
		k++;
	}
}

template<typename  T>
void __merge2(T aux[], T arr[], int l, int mid, int r) {

	for (int i = l; i <= r; i++)
		aux[i - l] = arr[i];

	int i = l, j = mid + 1;
	for (int k = l; k <= r; k++) {

		if (i > mid) { arr[k] = aux[j - l]; j++; }
		else if (j > r) { arr[k] = aux[i - l]; i++; }
		else if (aux[i - l] < aux[j - l]) { arr[k] = aux[i - l]; i++; }
		else { arr[k] = aux[j - l]; j++; }
	}
}

template <typename T>
void __mergeSort(T t[],T arr[], int l, int r) {//[l,r]区间对arr排序

	if (l>=r)
		return;
	/*if (r - l <= 15) {
		insertSort(arr, l, r);
		return;
	}*/

	int mid = (l + r) / 2;
	__mergeSort(t,arr, l, mid);
	__mergeSort(t,arr, mid + 1, r);
	__merge2(t, arr, l, mid, r);
	//__merge(t,arr, l, mid, r);
}

// merge sort from up to bottom
template <typename T>
void mergeSortUB(T arr[], int n) {
	T *t = new T[n];
	__mergeSort(t, arr, 0, n - 1);
	delete[] t;
}

// merge sort from bottom to up
template <typename T>
void mergeSortBU(T arr[], int n) {
	T *t = new T[n];
	for (int step = 1; step <= n; step += step) {
		for (int j = 0;(j + step) < n;j += 2 * step) {
			//__merge(arr, j, j + step - 1, min(n - 1, j + 2 * step - 1));
			__merge2(t,arr, j, j + step - 1, min(n - 1, j + 2 * step - 1));
		}
	}
	delete[] t;

}

#endif